package com.wc.alorithm.string.manacher;

/**
 * @Author congege
 * @Description Manaher算法，马拉车算法
 * 为解决一个字符串中最长回文字串长度O(n)的时间复杂的
 * @Date Created in 2023/12/1-16:55
 */
public class Main {
    // 步骤 1 ,在字符之间加入 # ,将偶数和奇数回文子串用同一类型代替
    private static String preHandleString(String s) {
        StringBuffer sb = new StringBuffer();
        char jin = '#';
        sb.append(jin);
        for (char c : s.toCharArray()) {
            sb.append(jin);
            sb.append(c);
        }
        sb.append(jin);
        return sb.toString();
    }

    // 寻找最长的回文子串
    private static String findLongestPalindromeString(String s) {
        // 第一步, 在字符串中加入‘#’
        String str = preHandleString(s);
        // 字串长度
        int lenStr = str.length();
        // 右边界
        int rightSide = 0;
        // 有边界对应的回文串中心
        int rightSideCenter = 0;
        // 保存以每个字符为中心的回文长度的一半（回文半径）
        int[] halfLenArr = new int[lenStr];
        // 记录回文中心
        int center = 0;
        // 记录最长回文半径
        int longestHalf = 0;

        for (int i = 0; i < lenStr; i++) {
            // 是否需要扩展
            boolean needCalc = true;
            // 如果有边界的覆盖之内
            if (i < rightSide) {
                // 计算右边界中的对应位置i' = 2 * rightSideCenter - i
                int leftCenter = 2 * rightSideCenter - i;
                // 根据回文性质的到结论
                halfLenArr[i] = halfLenArr[leftCenter];
                // 如果超过了有边界，进行调整, 超出的部分不一定是回文的
                if (i + halfLenArr[i] > rightSide) {
                    halfLenArr[i] = rightSide - i;
                }
                // 如果根据一致的计算得出的最长回文小于右边界，则不需要扩展了
                if (i + halfLenArr[leftCenter] < rightSide) {
                    needCalc = false;
                }
            }

            // 中心扩展
            if (needCalc) {
                // 左边界
                int left = i - halfLenArr[i] - 1;
                // 右边界
                int right = i + halfLenArr[i] + 1;
                while (left >= 0 && right < lenStr) {
                    if (str.charAt(left) == str.charAt(right)) {
                        halfLenArr[i]++;
                    } else {
                        break;
                    }
                    left = i - halfLenArr[i] - 1;
                    right = i + halfLenArr[i] + 1;
                }
                // 更新有边界以及中心
                if (i + halfLenArr[i] > rightSide) {
                    rightSide = i + halfLenArr[i];
                    rightSideCenter = i;
                }
                // 记录最长回文串
                if (halfLenArr[i] > longestHalf) {
                    center = i;
                    longestHalf = halfLenArr[i];
                }
            }
        }
        // 去掉之前添加的 '#'
        StringBuffer sb = new StringBuffer();
        int left = center - longestHalf + 1;
        int right = center + longestHalf - 1;
        for (int i = left; i <= right; i += 2) {
            sb.append(str.charAt(i));
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println(findLongestPalindromeString("bbaaaacccccaaaabbbbb"));
    }
}
